首先明确一点,所有装备的期望相同,只需求出任意一种后答案乘 即可。
令 表示还需要打 只怪,装备等级为 的金币数量期望。
那么有三种情况:
1.得到的并不是当前类型装备,概率为 ,这种情况下你一分钱也得不到。
2.得到当前装备的 级,概率为 ,然后你可以得到 元。
3.得到当前装备的 $[1,j] $ 级 ,概率为 。
此时金币的期望为 。
用滚动数组优化一下,这样可以 转移。
但是 , 我们得优化一下。
我们要相信 跟我一样非,装备等级不会太高。
理性计算一下:
由上面分析可得,装备由 级 到 级的概率为 ,那么期望次数为
记期望最高等级为 ,那么
解得:
理论上开 即可,但这样有 的误差,开 即可。
#include <cstdio>
const int MAXN = 525;
int n , k;
double dp[ 2 ][ MAXN + 5 ];
int main( ) {
scanf("%d %d",&n,&k);
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= MAXN ; j ++ )
dp[ i & 1 ][ j ] = ( dp[ ( i - 1 ) & 1 ][ j ] * ( ( k - 1 ) * 1.0 / k ) + ( dp[ ( i - 1 ) & 1 ][ j + 1 ] + j ) * ( 1.0 / ( k * ( j + 1 ) ) ) + ( dp[ ( i - 1 ) & 1 ][ j ] + ( 1 + j ) / 2.0 ) * ( j * 1.0 / ( k * ( j + 1 ) ) ) );
printf("%.10f\n", dp[ n & 1 ][ 1 ] * k );
return 0;
}